class Node(object):
    def__init__(self,item):
        self.item = item
        self.left = None
        self.right = None
    def __str__(self):
        return str(self,item)


class Tree(object):
    def __init__(self):
        self.root = Node('root')
    def add(self,item):
        Node Node(item)
        if self.root is None:#如果二叉树为空，那么生成的二叉树最终为新插入
            self.root = node
        else:
            q = [self.root]#将q列表添加二叉树的根节点
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)


def insertLeft(self,item):
    node = Node(item)
    if self.root.left is None:
        self.root.left = node
    else:
        node.left = self.root.left
        self.root.left = node
def insertRight(self,item):
    node = Node(item)
    if self.root.right is None:
        self.root.right = node
    else:
        node.right = self.root.left
        self.root.left = node
def get_parent(self,item):
    if self.root.item == item:
        return None#根节点没有父节点
    tmp = [self.root]
    while tmp:
        pop_node = tmp.pop(0)#某一点的左子树是寻找的点
        if pop_node.left and pop_node.left.item == item:
            return pop_node#返回某点，就是寻找的父节点
        if pop_node.right and pop_node.right.item == item:
            return pop_node
        if pop_node.left is not None:
            tmp.append(pop_node.left)
        if pop_node.right is not None:
            tmp.append(pop_node.right)
def delete(self,item):
    if self.root is None:
        return False
    parent = self.get_parent(item)
    if parent:
        del_node = print.left if print.left.item == item else parent.right
        if del_node.lefe is None:
            if print.left.item == item:
                parent.left = del_node.right
            else:
                parent.right = del_node.right
            del del_node
            return True
        elif del_node.right is None:
            if parent.left.item == item:
                parent.left = del_node.left
            else:
                parent.right = del_node.left
            del del_node
            return True
        else:
            tmp_pre = del_node
            tmp_next = del_node.right
            if tmp_next.left is None:
                tmp_pre.right = tmp_next.right
                tmp_next.left = del_node.left
                tmp_next.right = del_node.right
            else:
                while tmp_next.left:#将tmp指向右子树
                    tmp_pre = tmp_next
                    tmp_next = tmp_next.left
                tmp_pre.left = tmp_next.right
                tmp_next.left = del_node.left
                tmp_next.right = del_node.right
            if parent.left.item = =item:
                parent.left = tmp_next
            else:
                parent.right = tmp_next
            del del_node
            return True
        return False


t = Tree()
t.add(1)
t.add(2)
print(t.get_parent())
t.delete(1)
print(t.get_parent(4))





#pre order
ls[]
def pre(root):
    if not root:
        return
    ls.append(root.val)
    pre(root.left,ls)
    pre(root.right,ls)

    def mid(root,ls):
        if not root:
            return
        pre(root.left,ls)
        ls.append(root.val)
        pre(root.right,ls)
    def post(root,ls):
        if not root:
            return
        post(root.left,ls)
        post(root.right,ls)
        ls.append(root.val)

